package 回溯;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 优美的排列526.java
 * @createTime 2023年01月30日 19:31:00
 */
public class 优美的排列526 {
	int result = 0;

	public int countArrangement(int n) {
		backTrace(n, 1, new boolean[n + 1]);
		return result;
	}

	public void backTrace(int n, int curIndex, boolean[] used) {
		//结束条件，因为index是从1开始的所以如果n=2，那么结束就应该是1+2也就是n+1
		if (n + 1 == curIndex) {
			result++;
			return;
		}
		//从当前位置开始循环
		for (int i = 1; i < n + 1; i++) {
			//做选择，当前的被用来则跳过
			if (used[i]) {
				continue;
			}
			//当前数是否符合
			if (i % curIndex == 0 || curIndex % i == 0) {
				used[i] = true;
				backTrace(n, curIndex + 1, used);
				used[i] = false;
			}
		}
	}
}
